package com.cookie.study.algorithm.array;

/**
 * Created by zhangbo on 2020/12/16
 */
public class ArrayTest {
    public static void main(String[] args) {

    }
    /**
     * 数组中重复的数字
     * 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。
     * 数组中某些数字是重复的，但不知道有几个数字是重复的，
     * 也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
     */
    public int duplicate(int[] arr){
        int n =arr.length;
        if(n<=1){
            return -1;
        }

        for(int i=0;i<n;i++){
            while(i != arr[i]){
                if(arr[i] == arr[arr[i]]){
                   return arr[i];
                } else {
                    swap(arr,i,arr[i]);
                }
            }
        }
        return -1;
    }

    /**
     *二维数组中的查找
     * 给定一个二维数组，其每一行从左到右递增排序，
     * 从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。
     */
    public boolean find(int[][] arr,int val){
        int row =arr.length;
        int col =arr[0].length;
        int startRow = 0;
        int statCol = col-1;
        int num = arr[startRow][statCol];

        while(row>=0 && col>=0){
            if(val == num){
                return true;
            } else if(val>num){
                num = arr[startRow][startRow--];
            } else {
                for(int i =0;i<statCol;i++){
                    if(arr[startRow][statCol] > val){
                        continue;
                    }else if(arr[startRow][statCol] == val){
                        return true;
                    }else {
                        return false;
                    }
                }
            }
        }
        return false;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}
